package Greedy.leetcode;

/**
 * 1. 问题描述
 *      假设你有一个很长的花坛，一部分地块种植了花，另一部分却没有。
 *      可是，花卉不能种植在相邻的地块上，它们会争夺水源，两者都会死去。
 *      给定一个花坛（表示为一个数组包含0和1，其中0表示没种植花，1表示种植了花），
 *      和一个数n。能否在不打破种植规则的情况下种入n朵花？能则返回True，不能则返回False。
 *
 * 2. 算法分析
 *      1. 理解题意
 *          种花规则：
 *              相邻的花坛上不能都种花，我们用0表示没有种花，1表示种花
 *          我们给定一个的花坛，花坛上可能已经种了花(满足种花规则)，现在有n多花
 *          需要种在花坛上，判断在不改变种花的情况下，能否种植n朵花
 *
 *      2. 算法分析
 *         符号规定： flowered[] 表示花坛  长度为 m
 *          考虑什么条件下我们才能种下花? 假设现在我们想在第i个花坛的位置种花  此时考虑的是花坛的中间部位，之后考虑边界
 *          1. flowered[i] = 0   第i个花坛没有花，这是必须的
 *          2. flowered[i+1] = flowered[i-1] = 0  第i个花坛的左右都没有种值花
 *          i = 0 此时的条件就是flowered[i+1] = 0
 *          i = len - 1 此时的条件就是flowered[i-1] = 0
 *
 *          为了能种下最多的花，最好的种花策略就是隔一个种一个，但是这样有可能会破坏已有的种花
 *          所以我们需要加以判断
 *
 * 3. 代码实现
 *
 */
@SuppressWarnings("all")
public class 种花问题 {
    public static void main(String[] args) {
        int[] flowered = {1,0,0,0,1};
        boolean b = canPlaceFlowers(flowered, 2);
        System.out.println(b);

    }

    /**
     * 判断能否将n朵花种在花坛上
     * @param flowerbed：花坛
     * @param n：需要种植花的数量
     * @return
     */
    public static boolean canPlaceFlowers(int[] flowerbed, int n) {
        if(n == 0) {return true;}
        if(flowerbed.length == 1) {
            if(flowerbed[0] == 0 && n <= 1) {return true;}
            return false;
        }
        int count = 0; // 记录可以种植的花的数量
        for (int i = 0; i < flowerbed.length; i++) {
            if (i == 0) {
                if (flowerbed[i] == 0 && flowerbed[i+1] == 0) {
                    count++;
                    flowerbed[i] = 1;
                }
            } else if (i == flowerbed.length - 1) {
                if (flowerbed[i] == 0 && flowerbed[i-1] == 0) {
                    count++;
                    flowerbed[i] = 1;
                }
            } else {
                if (flowerbed[i-1] == 0 && flowerbed[i+1] == 0 && flowerbed[i] == 0) {
                    count++;
                    flowerbed[i] = 1;
                }
            }
        }
        return (count >= n) ? true : false;
    }

    public static boolean canPlaceFlowers2(int[] flowerbed,int n) {
        int i = 0, count = 0;
        while (i < flowerbed.length) {
            // 如果想要在当前花坛种种植花，首要条件就是当前花坛没有花，即flowerbed[i] = 0,当然这还不够，因为可能不满足条件
            // 1. 当前i = 0，flowerbed[i+1] = 0
            // 2. 当前i = len - 1，flowerbed[i-1] = 0
            // 3. 当前0 < i < len - 1，flowerbed[i-1] = flowerbed[i+1] = 0
            /*
                flowerbed[i] == 0 && i == 0 && flowerbed[i+1] == 0 // 首边界
                flowerbed[i] == 0 && i == len - 1 && flowerbed[i-1] == 0 // 尾边界
                flowerbed[i] == 0 && flowerbed[i-1] == 0 && flowerbed[i+1] == 0 // 中间部分
                将上述条件抽象出来
                flowerbed[i] == 0 && (i == 0 || flowerbed[i-1]) && (i == len - 1 || flowerbed[i+1])
            */
            if (flowerbed[i] == 0 && (i == 0 || flowerbed[i - 1] == 0) && (i == flowerbed.length - 1 || flowerbed[i + 1] == 0)) {
                flowerbed[i] = 1;
                count++;
            }
            i++;
        }
        return count >= n;
    }
}
